﻿#include "stdafx.h"
#include "KruskalMinimumSpanningTree.h"
#include <iostream>


void KruskalTree::CreateGraph(){
	std::cout << "input arc like this : a b 4" << std::endl;
	for(int i = 0; i < arc_num_; ++i){
		std::cout << "input arc [" << i+1 << "] :" ;
		char a,b;
		int w;
		std::cin >> a >> b  >> w ;
		weights_.push_back(std::make_pair(std::make_pair(a,b),w));
	}
}

KruskalTree::~KruskalTree(){
	delete [] father;
	delete [] rank;
}

//return his root
char KruskalTree::FindSet(char a){
	int index = a-'a';
	if(index != father[index]){
		father[index] = FindSet(father[index]+'a')-'a' ;
	}
	return father[index]+'a';
}

void KruskalTree::MakeSet(char a){
	int index = a-'a';
	father[index] = index;
	rank[index] = 0;
}

void KruskalTree::Union(char a, char b){
	int a_index = a - 'a';
	int b_index = b - 'a';
	if(a_index == b_index) return;
	//let the less rank's <root> be a child.
	if(rank[a_index] < rank[b_index]){
		father[FindSet(a_index+'a')-'a'] = b_index; 

	}else{
		if(rank[a_index] == rank[b_index])
			++rank[a_index];
		father[FindSet(b_index+'a')-'a'] = a_index;
	}
}
//kruskal 最小生成树，首先将每个结点看作是以其本身为根节点的树
//从而这些结点构成了一个森林
//算法每次从森林中，选出一个最短的边连接两棵树
//通过findset 确定两个结点是否存在于同一棵树
//通过union 合并两棵树
int KruskalTree::GetKruskalTree(){
	int sum = 0;
	father = new int[node_num_];
	rank = new int[node_num_];
	for(int i = 0; i < node_num_; ++i){
		MakeSet('a'+i);
	}
	weights_.sort(node_cmp());	
	for(;;){
		if(weights_.empty()) break;
		cw_pair top = weights_.front();
		char a = top.first.first;
		char b = top.first.second;

		if(FindSet(a) != FindSet(b)){
			sum += top.second;
			std::cout << a << "--" << b << std::endl;
			Union(a, b);
		}
		weights_.pop_front();
	}
	return sum;
}